package interview.demo1;

/**
 * 快速排序:
 * 原理：选择一个数组值作为基准，从数组两边开始遍历整个数组，
 * 我们选取一个基准值，从右侧开始遍历，找到小于基准的数，
 * 就替换掉基准位的值，接下来从左开始遍历，找到大于基准的值，
 * 就填补右侧之前替换掉基准位的值的位置空缺，左右的遍历依次交换进行，
 * 直到左右两个遍历相遇，将基准值放入相遇的位置。此时左侧全部为小于基准的值，
 * 右侧全为大于基准的值。之后对于前后段的排序也递归采用前面的方式，直到排序结束。
 *
 * @author
 * @create 2018-10-12 14:12
 **/
public class QuickSore {


    public static void main(String[] args) {
        int[] array = {100, 4, 67, 5, 2, 7, 8, 6, 9, 44};

        System.out.println("排序前的数组：");
        for (int a : array) {
            System.out.print(a + " ");
        }
        QuickSore1(array, 0, array.length - 1);

        System.out.println();
        System.out.println("排序后的数组为：");
        for (int a : array) {
            System.out.print(a + " ");
        }
    }

    /**
     * 原生的快速排序：递归的方式
     * 思路： 1 先以中间的位置的值开始，找到所有把中间值大的放入右边，比中间值小的放入左边
     * 2 在对中间值左边的再进行一次递归排序
     * 3 在对右边的值进行一次递归排序
     *
     * @param array
     * @return
     */
    public static int[] QuickSore(int[] array, int left, int right) {
        int L = left;
        int R = right;

        int midNumber = (left + right) / 2;
        //中间数为支点
        int mid = array[midNumber];

        //从左边扫描都右边
        while (L <= R) {
            //有值比中间值大,找到比中间值大的数
            while (array[L] < mid) {
                L++;
            }
            //找到比中间值小的数
            while (mid < array[R]) {
                R--;
            }
            if (L <= R) {
                //将两个数进行替换
                int temp = array[L];
                array[L] = array[R];
                array[R] = temp;
                L++;
                R--;
            }

        }
        //这样下来，第一趟可以保证，中间数左边的都比中间数小，中间数右边的都比中间数大
        //这样下来，L++后实际上就是排序右边的第一个元素，R--就是排序左边的最后一个元素
        //例如：数组{1, 4,67, 5,  2, 7, 8, 6, 9, 44};
        //则排序完成后的数据为{1,4,6, 5, 2, 7, 8, 67, 9, 44}
        // 此时的L=3(值为5)，R为6(值为8),那么如果我们是left<L的话，排序到的只有{1,4,6,5}少了2，
        // 这样左边就肯定排序失败，因为你的右边界没有包括进去，所以必须为右边扫描过来的R才行

        //对中间数左边的进行排序:
        if (left < R) {
            array = QuickSore(array, 0, R);
        }

        //对中间数右边的进行排序
        if (L < right) {
            array = QuickSore(array, L, right);
        }
        return array;
    }


    public static void QuickSore1(int[] array, int left, int right) {
        //如果不满足左边小于右边，则直接退出该方法
        if (!(left < right)) return;
        int L = left;
        int R = right;

        //基准点
        int x = array[L];

        while (L < R) {
            //从右边开始寻找比基准点小的值
            while (array[R] > x && L < R) {
                R--;
            }
            if (L < R) {
                array[L] = array[R];
                L++;
            }

            //从左边开始寻找比基准点大的值
            while (array[L] < x && L < R) {
                L++;
            }
            if (L < R) {
                array[R] = array[L];
                R++;
            }

            //基准点移动到中间来
            array[L] = x;
             QuickSore1(array, left, L - 1);
            QuickSore1(array, L + 1, right);


        }
    }


    public static void quickSort(int[] source, int a, int b) {
        if (!(a < b)) return;
        int i = a;
        int j = b;
        int x = source[i];
        while (i < j) {
            //循环递减，直到i、j相遇或者出现小于基准数的值
            while (i < j && source[j] > x) {
                j--;
            }
            if (i < j) {
                source[i] = source[j];
                i++;
            }
            //循环递增，直到出现大于基准数的值
            while (i < j && source[i] < x) {
                i++;
            }
            if (i < j) {
                source[j] = source[i];
                j--;
            }
        }
        //将基准点位移到中间位置
        source[i] = x;
        System.out.println(source);
        //递归调用，基准点前的排序；之后进行基准点之后的排序
        quickSort(source, a, i - 1);
        quickSort(source, i + 1, b);
    }

}
